package leetcode.top100;


import utils.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @date 2020/2/28 20:33
 */
public class Code141_142_IsAnnulateList_有环链表 {
    public static ListNode isAunulateList1(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        while (p != null){
            if(set.contains(p)) return p;
            set.add(p);
            p = p.next;
        }
        return null;
    }
    public static ListNode isAunulateList2(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (true){
            //无环
            if(fast.next == null ||fast.next.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        fast = head;
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
    public static ListNode isAunulateList3(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (true){
            //无环
            if(fast.next == null ||fast.next.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        //统计环个数.
        int count = 1;
        fast = slow.next;
        while (fast != slow){
            fast = fast.next;
            count ++;
        }
        //先走count步，然后一起走一步，必定在入环相遇。
        slow = fast = head;
        while (count-- != 0){
            slow = slow.next;
        }
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
//        head1.next = new ListNode(2);
//        head1.next.next = new ListNode(3);
//        head1.next.next.next = new ListNode(4);
//        head1.next.next.next.next = new ListNode(5);
//        head1.next.next.next.next.next = new ListNode(6);
//        head1.next.next.next.next.next.next = new ListNode(7);
//        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
//
//        System.out.println(isAunulateList2(head1).value);

        // 1->2->3->4->5->6->7->4...
        head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next = new ListNode(6);
        head1.next.next.next.next.next.next = new ListNode(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4


        // 0->9->8->2...
        ListNode head2 = new ListNode(0);
        head2.next = new ListNode(9);
        head2.next.next = new ListNode(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(isAunulateList3(head1).val);
        System.out.println(isAunulateList3(head2).val);

    }
}
